package demo_leetcode_day;

/*
在上次打劫完一条街道之后和一圈房屋后，小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为“根”。 除了“根”之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。
计算在不触动警报的情况下，小偷一晚能够盗取的最高金额。
示例 1:
输入: [3,2,3,null,3,null,1]

     3
    / \
   2   3
    \   \
     3   1

输出: 7
解释: 小偷一晚能够盗取的最高金额 = 3 + 3 + 1 = 7.
示例 2:
输入: [3,4,5,1,3,null,1]

     3
    / \
   4   5
  / \   \
 1   3   1

输出: 9
解释: 小偷一晚能够盗取的最高金额 = 4 + 5 = 9.
*/

import java.util.HashMap;
import java.util.Map;

public class demo_20200805 {
    public static void main(String[] args) {
//        TreeNode node1 = new TreeNode(3);
//        TreeNode node2 = new TreeNode(2);
//        TreeNode node3 = new TreeNode(3);
//        TreeNode node4 = new TreeNode(3);
//        TreeNode node5 = new TreeNode(1);
//        node1.left = node2;
//        node1.right = node3;
//        node2.right = node4;
//        node3.right = node5;
        TreeNode node1 = new TreeNode(4);
        TreeNode node2 = new TreeNode(1);
        TreeNode node3 = new TreeNode(2);
        TreeNode node4 = new TreeNode(3);
        node1.left = node2;
        node2.left = node3;
        node3.left = node4;

        System.out.println(new Solution().rob(node1));
    }

    static public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    static class Solution {
        Map<TreeNode, Integer> dpF = new HashMap<>(); // 节点选择时，DP值
        Map<TreeNode, Integer> dpG = new HashMap<>(); // 节点不选择时，DP值

        public int rob(TreeNode root) {
            dfs(root);
            return Math.max(dpF.getOrDefault(root, 0), dpG.getOrDefault(root, 0)); // 根节点判断
        }

        // 深度遍历
        private void dfs(TreeNode node) {
            if (null == node) return;
            // 遍历处理
            dfs(node.left);
            dfs(node.right);
            // 当前节点选择时，DP为本节点 + 左右子节点
            dpF.put(node, node.val + dpG.getOrDefault(node.left, 0) + dpG.getOrDefault(node.right, 0));
            // 当前节点不选择时, DP为左右子节点的和，但是并不一定要选用，而是可用不可用，取其最大
            dpG.put(node, Math.max(dpG.getOrDefault(node.left, 0), dpF.getOrDefault(node.left, 0)) + Math.max(dpG.getOrDefault(node.right, 0), dpF.getOrDefault(node.right, 0)));
        }
    }

    // 以下逻辑错误，不能单纯的奇数偶数
//    static class Solution {
//        /**
//         * 思路，说白了就是奇数层和偶数层的数字和比较，谁大用谁的
//         */
//        int odd = 0; // 奇数和
//        int even = 0; // 偶数和
//
//        public int rob(TreeNode root) {
//            if (null == root) return 0;
//            List<List<TreeNode>> list = new ArrayList<>();
//            list.add(new ArrayList<TreeNode>() {{
//                add(root);
//            }});
//            int index = 0;
//            while (1 == 1) {
//                List<TreeNode> listLayer = list.get(index);
//                for (int i = 0; i < listLayer.size(); i++) {
//                    TreeNode node = listLayer.get(i);
//                    if (index % 2 == 0) {
//                        odd += node.val;
//                    } else {
//                        even += node.val;
//                    }
//                    // 子节点追加
//                    addNext(list, index, node);
//                }
//
//                index++;
//                // 判断是否要
//                if (list.size() <= index) {
//                    break;
//                }
//            }
//            return Math.max(odd, even);
//        }
//
//        // 追加下层
//        private void addNext(List<List<TreeNode>> list, int index, TreeNode node) {
//            if (null == node.left && null == node.right) return;
//            // 取得节点层
//            List<TreeNode> listLayer;
//            if (list.size() <= index + 1) {
//                listLayer = new ArrayList<>();
//                list.add(listLayer);
//            } else {
//                listLayer = list.get(index + 1);
//            }
//            // 左右节点追加
//            if (null != node.left) listLayer.add(node.left);
//            if (null != node.right) listLayer.add(node.right);
//        }
//    }
}
